package project.euler;

/**
 * The prime number is calculated using Sieve of Eratosthenes.
 * 
 * Make a list of all the integers less than or equal to n (and greater than one). 
 * Strike out the multiples of all primes less than or equal to the square root of n, 
 * then the numbers that are left are the primes. 
 * 
 * @author Shekhar
 *
 */
public class SieveOfEratosthenes_PrimeNumber {

	public static void main(String[] args) {
		printPrimes(10);
	}
	
	private static void printPrimes(int n){
		// create an array of boolean which describes that all the numbers till n are prime
		boolean[] primes = new boolean[n+1];
		for(int i = 2;i<=n;i++){
			primes[i] = true;
		}
		
		// start from the first divisor i.e. 2 and find all the multiples of the divisor and make them not prime. And after that move the next element 
		for(int divisor = 2;divisor*divisor < n; divisor++){
			if(primes[divisor] == true){
				for(int i = 2* divisor; i<=n;i = i + divisor)
					primes[i]= false;
				}
			}
		
		for(int i = 2;i<= n ;i++){
			if(primes[i]){
				System.out.println(i);
			}
		}
		
	}
}
	
